Роман Панов - Дерево смещений: работаем с динамически изменяемыми сегментированными массивами

Ближайшая конференция - C++ Russia 2025, 20-21 марта, Москва + online. Подробности и билеты: jrg.su/9Sszhd
- -
Скачать презентацию с сайта C++ Russia - jrg.su/aCyBLQ
Спикер рассказал про задачу, которую решал, и проблему, с которой столкнулся.
Есть большой список, например, история сообщений чата. Есть окно просмотра (viewport), в которое попадает лишь малая часть списка. Нужно рисовать только видимую часть - то, что попадает во viewport. Рисовать требуется часто, 30 раз в секунду, то есть нужно уметь быстро находить видимые элементы. Более того, сообщения могут редактироваться, а следовательно, менять свой размер и удаляться. Хуже того, есть анимация - сообщения плавно перемещаются по списку. Например, после удаления сообщения «хвост» плавно заполняет образовавшееся пространство. Другими словами, надо быть готовыми к тому, что геометрия списка меняется каждый кадр.
Он описал несколько «наивных» решений с использованием стандартных контейнеров. Объясню, почему они неэффективны. Представил эффективное решение с помощью так называемого дерева смещений (не путать с деревом отрезков - это другая структура данных).
Будет интересно тем, кто интересуется алгоритмами визуализации больших списков данных. Покажу реализацию дерева смещений на C++, как с помощью шаблонов сделать реализацию универсальной и настраиваемой.